#include <bits/stdc++.h>
using namespace std;

/*
3169. 无需开会的工作日
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

 

示例 1：

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]

输出：2

解释：

第 4 天和第 8 天没有安排会议。

示例 2：

输入：days = 5, meetings = [[2,4],[1,3]]

输出：1

解释：

第 5 天没有安排会议。

示例 3：

输入：days = 6, meetings = [[1,6]]

输出：0

解释：

所有工作日都安排了会议。

 

提示：

1 <= days <= 109
1 <= meetings.length <= 105
meetings[i].length == 2
1 <= meetings[i][0] <= meetings[i][1] <= days
*/

// 法一
class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        // 过滤所有开始时间大于总天数的会议
        vector<vector<int>> filter;
        for (auto& meet : meetings) {
            if (meet[0] <= days)    filter.push_back(meet);
        }
        // 没有有效会议 都可以工作
        if (filter.empty())     return days;
        // 时间升序 便于区间合并
        sort(filter.begin(), filter.end());

        int cur_start = filter[0][0];       // 起始日
        int cur_end = filter[0][1];       // 结束日
        int tot = 0;

        // 遍历 合并重叠或者连续
        for (int i = 1; i < filter.size(); i++) {
            // 当前有重叠或者连续 取较大
            if (filter[i][0] <= cur_end + 1)    cur_end = max(cur_end, filter[i][1]);
            else {
                // 结算当前合并
                int endhe = min(cur_end, days);
                tot += (endhe - cur_start + 1);

                // 新的合并区间
                cur_start = filter[i][0];
                cur_end = filter[i][1];
            }
        }
        // 最后一个合并区间
        int endhe = min(cur_end, days);
        tot += (endhe - cur_start + 1);

        return days - tot;
    }
};

// 法二
class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        // 按会议开始时间升序排序，便于后续合并重叠区间
        sort(meetings.begin(), meetings.end(), [](auto & e1, auto & e2){
            return e1[0] < e2[0]; // 优先比较开始时间，开始早的排前面
        });
        int ans = 0;        // 空闲天数
        int pre_end = 0;    // 已经合并的区间的最大结束时间

        // 遍历排序后的会议区间  合并重叠或连续的 计算空闲
        for (auto& meet : meetings) {
            // case1 当前与前面不重叠或连续
            if (meet[0] > pre_end + 1) {
                // 避免连续 造成误判
                ans += meet[0] - pre_end - 1;   // 累加
            }
            // 更新
            pre_end = max(pre_end, meet[1]);
        }
        ans += days - pre_end;  // max的处理保证了正确性
        return ans;
    }
};